package com.hyc.DataStructure.LinkedList;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.LinkedList
 * @className: DoubleLinkedListDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/19 15:38
 * @version: 1.0
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        System.out.println("双向链表测试");
        //创建链表对象
        ListNode ListNode = new ListNode(1, "宋江", "及时雨");
        ListNode ListNode1 = new ListNode(2, "卢俊义", "玉麒麟");
        ListNode ListNode2 = new ListNode(3, "吴用", "智多星");
        ListNode ListNode3 = new ListNode(4, "林冲", "豹子头");
        //创建双向链表
        DoubleLinkedList list = new DoubleLinkedList();
        //双向链表新增数组
        list.add(ListNode);
        list.add(ListNode1);
        list.add(ListNode2);
        list.add(ListNode3);
        //输出
        list.List();
        //修改
        ListNode ListNode4 = new ListNode(4, "公孙胜", "入云龙");
        list.updateNode(ListNode4);
        System.out.println("输出修改过后的链表");
        list.List();
        //    删除
        list.DeleteNode(3);
        System.out.println("删除指定节点的链表");
        list.List();
    }
}

class DoubleLinkedList {
    //创建一个头结点
    ListNode head = new ListNode(0, "", "");

    public ListNode getHead() {
        return head;
    }

    public void setHead(ListNode head) {
        this.head = head;
    }

    //遍历链表
    public void List() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head.next;
        while (true) {
            //遍历为空就代表找了最后一个节点
            if (temp == null) {
                break;
            }
            //输出节点
            System.out.println(temp);
            //后移一位
            temp = temp.next;
        }
    }

    //加入双向链表
    public void add(ListNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //指向下一个节点
        temp.next = node;
        //指向上一个节点
        node.pre = temp;
    }

    //修改双向链表，和单向链表基本一致不需要过多的修改
    //修改节点信息
    public void updateNode(ListNode newlistnode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改，我用 temp 来指向头结点
        ListNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newlistnode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //  true 修改信息
            temp.NickName = newlistnode.NickName;
            temp.Name = newlistnode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newlistnode.No);
        }
    }

    /*
     * 双向链表删除
     * 对于双向链表来说就不需要找到上一个节点来删除了，
     * 可以找到自己删除
     * */
    public void DeleteNode(int no) {
        if (head.next == null) {
            System.out.println("链表为空 不需要删除");
            return;
        }
        ListNode temp = head.next;
        // 用来标注 是不是可以删除
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.next.No == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除，这里我们只需要指向空 GC会回收
            //temp.next = temp.next.next; 原先的单向链表删除现在在双向链表里就不好使了
            /*将当前节点的上一个节点的下一个指向 指向当前节点的下一个节点 相当于向前指向的next 直接跨过当前的节点指向下一个节点*/
            temp.pre.next = temp.next;
            /*将当前节点的下一个节点的上一个指向 指向当前节点的上一个节点，相当于向前的pre 直接快过当前的节点指向上一个
             * 如果当前节点是最后一节点，就不执行后面这个将下一个节点的指向更改，不然会出现空指针
             * */
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
            /*这两步 坐完相当于 此时的当前节点已经没有了指向 会被回收*/
        } else {
            System.out.printf("要删除的 %d 没有找到", no);
        }
    }
}

/**
 * 双向链表要用的节点
 * */
class ListNode {
    //排名
    public int No;
    // 姓名
    public String Name;
    //昵称
    public String NickName;
    // 下一个节点
    public ListNode next;
    //上一个节点
    public ListNode pre;

    public ListNode(int hNo, String hName, String hNickName) {
        this.No = hNo;
        this.Name = hName;
        this.NickName = hNickName;
    }

    //方便输出语句输出
    @Override
    public String toString() {
        return "HeroNode{" +
                "No=" + No +
                ", Name='" + Name + '\'' +
                ", NickName='" + NickName + '\'' +
                '}';
    }
}